/*******************************************************************************
Description:  Defines a ReadyList class, which is one of the main data
              structures that an instruction scheduler needs. The ready list is
              a sored list of instructions whose data dependences have been
              satisfied (their predecessors in the data dependence graph have
              been scheduled).
Author:       Ghassan Shobaki
Created:      Apr. 2002
Last Update:  Mar. 2011
*******************************************************************************/

#ifndef OPTSCHED_BASIC_READY_LIST_H
#define OPTSCHED_BASIC_READY_LIST_H

#include <cstdio>
#include "llvm/CodeGen/OptSched/generic/defines.h"
#include "llvm/CodeGen/OptSched/generic/lnkd_lst.h"
#include "llvm/CodeGen/OptSched/basic/sched_basic_data.h"

namespace opt_sched {

// A priority list of instruction that are ready to schedule at a given point
// during the scheduling process.
class ReadyList {
  public:
    // A set of flags that determines which aspects of instructions are taken
    // into account when sorting the priority list.
    struct Priorities {
      // The instruction's critical path measured from the leaf.
      bool criticalPath;
      // The number of successors that the instruction has.
      bool successorCount;
      // The sum of latencies of the outgoing edges from the inst. in the DAG.
      bool latencySum;
      // The instruction's original program order (node ID).
      bool nodeID;
      // Whether to take resource constraints into account.
      bool accountForRsrcs;
      // The instruction's order in the input file.
      bool fileSchedOrder;
    };

    // Constructs a ready list for the specified dependence graph with the
    // specified priorities.
    ReadyList(DataDepGraph* dataDepGraph, Priorities prirts);
    // Destroys the ready list and deallocates the memory used by it.
    ~ReadyList();

    // Resets the list and removes all elements from it.
    void Reset();

    // Adds an instruction to the ready list.
    void AddInst(SchedInstruction* inst);

    // Adds a list of instructions to the ready list.
    void AddList(LinkedList<SchedInstruction>* lst);

    // An iterator that allows accessing the instructions at the current time
    // in priority order. The first call will return the top priority
    // instruction, the next will return the instruction with the second rank,
    // and so on.
    SchedInstruction* GetNextPriorityInst();

    // Removes the instruction returned by the last call to
    // GetNextPriorityInst().
    void RemoveNextPriorityInst();

    // Returns the number of instructions currently in the list.
    InstCount GetInstCnt() const;

    // Resets the list iterator to point back to the first instruction.
    void ResetIterator();

    // Adds instructions at the bottoms of the given two lists which have
    // not been added to the ready list already, and advance the internal time.
    // TODO(max): Elaborate.
    void AddLatestSubLists(LinkedList<SchedInstruction>* lst1,
                           LinkedList<SchedInstruction>* lst2);

    // Removes the most recently added sublist of instructions.
    // TODO(max): Elaborate.
    void RemoveLatestSubList();

    // Copies this list to another. Both lists must be empty.
    void CopyList(ReadyList* otherLst);

    // Searches the list for an instruction, returning whether it has been found
    // or not and writing the number of times it was found into hitCnt.
    bool FindInst(SchedInstruction* inst, int& hitCnt);

    // Prints out the ready list, nicely formatted, into an output stream.
    void Print(std::ostream& out);

  private:
    // The flagset determining which priorities to take into account.
    Priorities prirts_;
    // The priority list containing the actual instructions.
    PriorityList<SchedInstruction>* prirtyLst_;
    // TODO(max): Document.
    LinkedList<SchedInstruction>* latestSubLst_;

    // The maximum values for each part of the priority key.
    InstCount maxCrtclPath_;
    InstCount maxScsrCnt_;
    InstCount maxLtncySum_;
    InstCount maxNodeID_;
    InstCount maxFileSchedOrder_;

    // The number of bits for each part of the priority key.
    int16_t crtclPathBits_;
    int16_t scsrCntBits_;
    int16_t ltncySumBits_;
    int16_t nodeID_Bits_;
    int16_t fileSchedOrderBits_;

    // Constructs the priority-list key from the criteria enabled in prirts_.
    // The criteria in order (higher priority first) are:
    // 0. The instruction's basic block number.
    // 1. The instruction's critical path measured from the leaf.
    // 2. The instruction's weighted critical path from all branches.
    // 3. The instruction's issue type (give priority to the critical type).
    // 4. The instruction's weight.
    // 5. The number of successors that the instruction has.
    // 6. The sum of latencies of the outgoing edges from the inst. in the DAG.
    // 7. The instruction's original program order (node ID).
    // 8. The instruction's order in the input file.
    unsigned long CmputKey_(SchedInstruction* inst);

    // Adds instructions at the bottom of a given list which have not been added
    // to the ready list already.
    void AddLatestSubList_(LinkedList<SchedInstruction>* lst);

    // Calculates a new priority key given an existing key of size keySize by
    // appending bitCnt bits holding the value val, assuming val < maxVal.
    static void AddPrirtyToKey_(unsigned long& key,
                                int16_t& keySize,
                                int16_t bitCnt,
                                unsigned long val,
                                unsigned long maxVal);
};

} // end namespace opt_sched

#endif
